package likou;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/07/24 23:15
 */
public class _221 {
    
    public static void main(String[] args) {
        System.out.println(maximalSquare(new char[][]{{'0','0','0','1'},{'1','1','0','1'},{'1','1','1','1'},{'0','1','1','1'},{'0','1','1','1'}}));
    }
    
    public static int maximalSquare(char[][] matrix) {
        if(matrix.length==0) return 0;
        int gao = matrix.length;
        int kuan = matrix[0].length;
        List<Integer> startList = new ArrayList<>();
        int res = 0;
        for(int i=0;i<gao;i++){
            for(int j=0;j<kuan;j++){
                if(matrix[i][j]=='1'){
                    if(i<gao-1&&j<kuan-1){
                        startList.add(i*1000+j);
                    }
                    res = 1;
                }
            }
        }
        for(int i=1;i<300;i++){
            List<Integer> nextStartList = new ArrayList<>();
            no:for(int start:startList){
                int left = start%1000;
                int top = start/1000;
                int right = left+i;
                int bottom = top+i;
                if(right>=kuan||bottom>=gao) continue;
                if(matrix[bottom][right]=='0') continue;
                for(int j=right-1;j>=left;j--){
                    if(matrix[bottom][j]=='0')
                        continue no;
                }
                for(int j=bottom-1;j>=top;j--){
                    if(matrix[j][right]=='0')
                        continue no;
                }
                res=i+1;
                if(right<kuan-1&&bottom<gao-1){
                    nextStartList.add(top*1000+left);
                }
            }
            startList = nextStartList;
            if(startList.size()==0) break;
        }
        return res*res;
    }
}
